/*
 * @lc app=leetcode.cn id=459 lang=typescript
 *
 * [459] 重复的子字符串
 */

// @lc code=start
function repeatedSubstringPattern(s: string): boolean {
  const n = s.length;
  const next = new Array(n).fill(-1);
  let j = -1;
  // 计算next数组，最长公共前后缀
  for (let i = 1; i < n; i++) {
    while (j !== -1 && s[i] !== s[j + 1]) {
      j = next[j];
    }
    if (s[i] === s[j + 1]) {
      j++;
    }
    next[i] = j;
  }

  // 最后一位有公共前缀且公共前缀可以被字符串平均分割
  return next[n - 1] !== -1 && n % (n - next[n - 1] - 1) === 0;
}
// @lc code=end
